\contentsline {chapter}{Abstract}{i}{dummy.2}
\vspace {1em}
\contentsline {chapter}{Acknowledgements}{ii}{dummy.3}
\vspace {1em}
\contentsline {chapter}{Contents}{iii}{dummy.4}
\contentsline {chapter}{List of Figures}{v}{dummy.6}
\contentsline {chapter}{Abbreviations}{vi}{dummy.8}
\vspace {2em}
\contentsline {chapter}{\numberline {1}Introduction}{1}{chapter.11}
\contentsline {section}{\numberline {1.1}Radio Astronomy}{1}{section.12}
\contentsline {section}{\numberline {1.2}SKA and South Africa}{1}{section.13}
\contentsline {section}{\numberline {1.3}Compression Scheme Chosen}{2}{section.14}
\contentsline {section}{\numberline {1.4}Research Questions}{2}{section.15}
\contentsline {section}{\numberline {1.5}Report Structure}{3}{section.19}
\contentsline {chapter}{\numberline {2}Background}{4}{chapter.20}
\contentsline {section}{\numberline {2.1}Square Kilometer Array in South Africa}{4}{section.21}
\contentsline {section}{\numberline {2.2}Compression Schemes}{5}{section.23}
\contentsline {subsection}{\numberline {2.2.1}Basic Methods}{5}{subsection.24}
\contentsline {subsection}{\numberline {2.2.2}Statistical Methods}{5}{subsection.25}
\contentsline {subsection}{\numberline {2.2.3}Transformations}{6}{subsection.26}
\contentsline {subsection}{\numberline {2.2.4}Dictionary Methods}{6}{subsection.27}
\contentsline {section}{\numberline {2.3}Entropy Encoders}{6}{section.28}
\contentsline {section}{\numberline {2.4}Huffman Coding Overview}{7}{section.29}
\contentsline {section}{\numberline {2.5}Huffman Coder Extensions}{10}{section.33}
\contentsline {section}{\numberline {2.6}Parallelism}{10}{section.34}
\contentsline {subsection}{\numberline {2.6.1}Parallelism via the CPU}{11}{subsection.35}
\contentsline {subsection}{\numberline {2.6.2}Parallelism via the GPU}{11}{subsection.36}
\contentsline {chapter}{\numberline {3}Design}{13}{chapter.37}
\contentsline {section}{\numberline {3.1}Overview}{13}{section.38}
\contentsline {section}{\numberline {3.2}Algorithms}{14}{section.39}
\contentsline {subsection}{\numberline {3.2.1}Huffman Coding}{14}{subsection.40}
\contentsline {subsection}{\numberline {3.2.2}Adaptive Huffman Coding}{16}{subsection.85}
\contentsline {section}{\numberline {3.3}Prefix Sum}{17}{section.87}
\contentsline {section}{\numberline {3.4}GPU based Huffman Coding}{18}{section.88}
\contentsline {section}{\numberline {3.5}Benchmarking}{18}{section.89}
\contentsline {chapter}{\numberline {4}Adaptive Huffman Implementation}{20}{chapter.90}
\contentsline {section}{\numberline {4.1}Tree Structure}{20}{section.91}
\contentsline {section}{\numberline {4.2}Encoding Procedure}{20}{section.116}
\contentsline {section}{\numberline {4.3}Update Procedure}{22}{section.165}
\contentsline {section}{\numberline {4.4}Feasibility of AHC}{23}{section.185}
\contentsline {chapter}{\numberline {5}Huffman Coding Implementation}{24}{chapter.186}
\contentsline {section}{\numberline {5.1}CPU Only Huffman Coding}{24}{section.187}
\contentsline {subsection}{\numberline {5.1.1}Binning}{24}{subsection.188}
\contentsline {subsection}{\numberline {5.1.2}Tree Construction and Code Generation}{25}{subsection.203}
\contentsline {subsection}{\numberline {5.1.3}Float-to-code swapping procedure}{26}{subsection.233}
\contentsline {subsection}{\numberline {5.1.4}Binary Sequence to Char conversion}{26}{subsection.262}
\contentsline {subsection}{\numberline {5.1.5}Decompression}{27}{subsection.328}
\contentsline {section}{\numberline {5.2}GPU and CPU combined Huffman Scheme}{28}{section.329}
\contentsline {subsection}{\numberline {5.2.1}Binning}{29}{subsection.330}
\contentsline {subsection}{\numberline {5.2.2}Symbol to Code Swapping}{30}{subsection.354}
\contentsline {subsection}{\numberline {5.2.3}Binary sequence to Character array conversion}{31}{subsection.355}
\contentsline {subsection}{\numberline {5.2.4}Feasibility of Huffman Coding}{31}{subsection.392}
\contentsline {chapter}{\numberline {6}Results}{33}{chapter.393}
\contentsline {section}{\numberline {6.1}Tests}{33}{section.394}
\contentsline {subsection}{\numberline {6.1.1}Feasibility of Huffman Coding in parallel}{33}{subsection.395}
\contentsline {subsection}{\numberline {6.1.2}Comparison to standard compression programs}{34}{subsection.397}
\contentsline {subsection}{\numberline {6.1.3}Comparison of all SKA compression projects}{34}{subsection.400}
\contentsline {section}{\numberline {6.2}Discussion}{35}{section.404}
\contentsline {subsection}{\numberline {6.2.1}Feasibility of Huffman Coding in parallel and for SKA}{35}{subsection.405}
\contentsline {subsection}{\numberline {6.2.2}Comparison to Standard Compression programs}{37}{subsection.406}
\contentsline {subsection}{\numberline {6.2.3}Comparison of SKA compression projects}{38}{subsection.407}
\contentsline {chapter}{\numberline {7}Conclusion}{40}{chapter.408}
\vspace {2em}
\vspace {2em}
\contentsline {chapter}{Bibliography}{42}{dummy.412}
